// Copyright (c) 2025 guyuemeng
//
// cxxaux is licensed under Mulan PSL v2.
// You can use this software according to the terms and conditions of the Mulan
// PSL v2. You may obtain a copy of Mulan PSL v2 at:
//             http://license.coscl.org.cn/MulanPSL2
//
// THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY
// KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO
// NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
//
// See the Mulan PSL v2 for more details.

#ifndef ESTD___CONTAINER_FLAT_VECTOR_H
#define ESTD___CONTAINER_FLAT_VECTOR_H
#include <algorithm>
#include <iterator>
#include <type_traits>

namespace es {

struct __flat_vector_default_out_of_range_assert {
  constexpr void operator()(bool cond, const char* const msg) const {}
};

template <std::size_t N, typename T,
          typename OutOfRangeAssert = __flat_vector_default_out_of_range_assert>
class flat_vector {
  static constexpr inline OutOfRangeAssert out_of_range_assert{};

public:
  using value_type = T;
  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;
  using reference = value_type&;
  using const_reference = const value_type&;
  using pointer = value_type*;
  using const_pointer = const value_type*;
  using iterator = pointer;
  using const_iterator = const_pointer;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;

  constexpr flat_vector() noexcept : cursor_(data_) {}

  constexpr explicit flat_vector(size_type n) {
    out_of_range_assert(n <= N, "flat_vector size is out of range");
    cursor_ = data_ + n;
  }

  constexpr flat_vector(size_type n, const T& value) {
    out_of_range_assert(n <= N, "flat_vector size is out of range");
    cursor_ = data_ + n;
    std::fill(data_, cursor_, value);
  }

  template <typename InputIterator,
            typename = std::void_t<
                typename std::iterator_traits<InputIterator>::value_type>>
  constexpr flat_vector(InputIterator first, InputIterator last) {
    out_of_range_assert(std::distance(first, last) <= N,
                        "flat_vector size is out of range");
    cursor_ = std::copy(first, last, data_);
  }

  constexpr flat_vector(std::initializer_list<T> il) {
    out_of_range_assert(il.size() <= N, "flat_vector size is out of range");
    cursor_ = std::copy(il.begin(), il.end(), data_);
  }

  constexpr flat_vector(const flat_vector& other) {
    cursor_ = std::copy(other.begin(), other.end(), data_);
  }

  constexpr flat_vector(flat_vector&& other) noexcept {
    cursor_ = std::move(other.begin(), other.end(), data_);
  }

  constexpr flat_vector& operator=(const flat_vector& other) {
    if (this != &other) {
      cursor_ = std::copy(other.begin(), other.end(), data_);
    }
    return *this;
  }

  constexpr flat_vector& operator=(flat_vector&& other) noexcept {
    cursor_ = std::move(other.begin(), other.end(), data_);
    return *this;
  }

  ~flat_vector() noexcept = default;

  constexpr void assign(size_type n, const T& value) {
    out_of_range_assert(n <= N, "flat_vector size is out of range");
    cursor_ = data_ + n;
    std::fill(data_, cursor_, value);
  }

  template <typename InputIterator,
            typename = std::void_t<
                typename std::iterator_traits<InputIterator>::value_type>>
  constexpr void assign(InputIterator first, InputIterator last) {
    out_of_range_assert(std::distance(first, last) <= N,
                        "flat_vector size is out of range");
    cursor_ = std::copy(first, last, data_);
  }

  constexpr void assign(std::initializer_list<T> il) {
    out_of_range_assert(il.size() <= N, "flat_vector size is out of range");
    cursor_ = std::copy(il.begin(), il.end(), data_);
  }

  template <typename RangeT>
  constexpr void assign_range(const RangeT& range) {
    auto first = std::begin(range);
    auto last = std::end(range);
    out_of_range_assert(std::distance(first, last) <= N,
                        "flat_vector size is out of range");
    cursor_ = std::copy(first, last, data_);
  }

  constexpr reference at(size_type pos) {
    if (pos >= size()) {
      throw std::out_of_range("flat_vector::at() out of range");
    }
    return data_[pos];
  }

  constexpr const_reference at(size_type pos) const {
    if (pos >= size()) {
      throw std::out_of_range("flat_vector::at() out of range");
    }
    return data_[pos];
  }

  constexpr reference operator[](size_type pos) { return data_[pos]; }

  constexpr const_reference operator[](size_type pos) const {
    return data_[pos];
  }

  constexpr reference front() { return *data_; }

  constexpr const_reference front() const { return *data_; }

  constexpr reference back() { return *(cursor_ - 1); }

  constexpr const_reference back() const { return *(cursor_ - 1); }

  constexpr T* data() noexcept { return data_; }

  constexpr const T* data() const noexcept { return data_; }

  constexpr iterator begin() noexcept { return data_; }

  constexpr const_iterator begin() const noexcept { return data_; }

  constexpr const_iterator cbegin() const noexcept { return data_; }

  constexpr iterator end() noexcept { return cursor_; }

  constexpr const_iterator end() const noexcept { return cursor_; }

  constexpr const_iterator cend() const noexcept { return cursor_; }

  constexpr reverse_iterator rbegin() noexcept {
    return reverse_iterator(cursor_);
  }

  constexpr const_reverse_iterator rbegin() const noexcept {
    return const_reverse_iterator(cursor_);
  }

  constexpr const_reverse_iterator crbegin() const noexcept {
    return const_reverse_iterator(cursor_);
  }

  constexpr reverse_iterator rend() noexcept { return reverse_iterator(data_); }

  constexpr const_reverse_iterator rend() const noexcept {
    return const_reverse_iterator(data_);
  }

  constexpr const_reverse_iterator crend() const noexcept {
    return const_reverse_iterator(data_);
  }

  constexpr bool empty() const noexcept { return data_ == cursor_; }

  constexpr size_type size() const noexcept { return cursor_ - data_; }

  constexpr size_type max_size() const noexcept { return N; }

  constexpr void reserve(size_type new_cap) = delete;

  constexpr size_type capacity() const noexcept { return N; }

  constexpr void shrink_to_fit() = delete;

  constexpr void clear() noexcept { cursor_ = data_; }

  constexpr iterator insert(const_iterator pos, const T& value) {
    out_of_range_assert(pos >= begin() && pos <= end(),
                        "flat_vector insert out of range");
    if (cursor_ == std::end(data_)) {
      throw std::out_of_range("flat_vector insert out of range");
    }
    auto new_pos = begin() + std::distance(cbegin(), pos);
    std::copy_backward(new_pos, end(), cursor_ + 1);
    *new_pos = value;
    ++cursor_;
    return new_pos;
  }

  constexpr iterator insert(const_iterator pos, T&& value) {
    out_of_range_assert(pos >= begin() && pos <= end(),
                        "flat_vector insert out of range");
    if (cursor_ == std::end(data_)) {
      throw std::out_of_range("flat_vector insert out of range");
    }
    auto tmp = const_cast<iterator>(pos);
    std::copy_backward(tmp, cursor_, cursor_ + 1);
    *tmp = std::move(value);
    ++cursor_;
    return tmp;
  }

  constexpr iterator insert(const_iterator pos, size_type count,
                            const T& value) {
    out_of_range_assert(pos >= begin() && pos <= end(),
                        "flat_vector insert out of range");
    if ((cursor_ + count) > std::end(data_)) {
      throw std::out_of_range("flat_vector insert out of range");
    }
    auto new_pos = begin() + std::distance(cbegin(), pos);
    std::copy_backward(new_pos, end(), cursor_ + count);
    std::fill(new_pos, new_pos + count, value);
    cursor_ += count;
    return new_pos;
  }

  template <typename InputIterator>
  constexpr iterator insert(const_iterator pos, InputIterator first,
                            InputIterator last) {
    out_of_range_assert(pos >= begin() && pos <= end(),
                        "flat_vector insert out of range");
    size_type range_size = std::distance(first, last);
    if ((size() + range_size) > capacity()) {
      throw std::out_of_range("flat_vector insert out of range");
    }

    auto new_pos = begin() + std::distance(cbegin(), pos);
    std::copy_backward(new_pos, end(), end() + range_size);
    std::copy(first, last, new_pos);
    cursor_ += range_size;
    return new_pos;
  }

  constexpr iterator insert(const_iterator pos, std::initializer_list<T> il) {
    return insert(pos, il.begin(), il.end());
  }

  template <typename RangeT>
  constexpr iterator insert_range(const_iterator pos, const RangeT& range) {
    return insert(pos, std::begin(range), std::end(range));
  }

  template <typename... Args>
  constexpr iterator emplace(const_iterator pos, Args&&... args) {
    out_of_range_assert(pos >= begin() && pos <= end(),
                        "flat_vector emplace out of range");
    if (cursor_ == std::end(data_)) {
      throw std::out_of_range("flat_vector emplace out of range");
    }
    auto tmp = const_cast<iterator>(pos);
    std::copy_backward(tmp, cursor_, cursor_ + 1);
    *tmp = T(std::forward<Args>(args)...);
    ++cursor_;
    return tmp;
  }

  constexpr iterator erase(const_iterator pos) {
    out_of_range_assert(pos >= begin() && pos < end(),
                        "flat_vector erase out of range");
    auto tmp = const_cast<iterator>(pos);
    std::copy(tmp + 1, cursor_, tmp);
    --cursor_;
    return tmp;
  }

  constexpr iterator erase(const_iterator first, const_iterator last) {
    out_of_range_assert(first <= last, "flat_vector erase invalid range");
    out_of_range_assert(first >= begin(), "flat_vector erase out of range");
    out_of_range_assert(last <= end(), "flat_vector erase out of range");
    iterator range_first = begin() + std::distance(cbegin(), first);
    iterator range_last = begin() + std::distance(cbegin(), last);
    std::copy(range_last, end(), range_first);
    cursor_ -= std::distance(first, last);
    return range_first;
  }

  constexpr void push_back(const T& value) {
    if (cursor_ == std::end(data_)) {
      throw std::out_of_range("flat_vector push_back out of range");
    }
    *cursor_ = value;
    ++cursor_;
  }

  constexpr void push_back(T&& value) {
    if (cursor_ == std::end(data_)) {
      throw std::out_of_range("flat_vector push_back out of range");
    }
    *cursor_ = std::move(value);
    ++cursor_;
  }

  template <typename... Args>
  constexpr reference emplace_back(Args&&... args) {
    if (cursor_ == std::end(data_)) {
      throw std::out_of_range("flat_vector emplace_back out of range");
    }
    *cursor_ = T(std::forward<Args>(args)...);
    ++cursor_;
    return *(cursor_ - 1);
  }

  template <typename RangeT>
  constexpr void append_range(const RangeT& range) {
    auto first = std::begin(range);
    auto last = std::end(range);
    out_of_range_assert(std::distance(first, last) <=
                            std::distance(cursor_, std::end(data_)),
                        "flat_vector append_range out of range");
    cursor_ = std::copy(first, last, cursor_);
  }

  constexpr void pop_back() {
    if (cursor_ == std::begin(data_)) {
      throw std::out_of_range("flat_vector pop_back out of range");
    }
    --cursor_;
  }

  constexpr void resize(size_type count) { resize(count, T{}); }

  constexpr void resize(size_type count, const T& value) {
    out_of_range_assert(count <= N, "flat_vector resize out of range");
    if (count > size()) {
      std::fill(cursor_, data_ + count, value);
    }
    cursor_ = data_ + count;
  }

  template <typename Operation>
  constexpr void resize_and_overwrite(size_type count, Operation op) {
    auto size = op(data_, capacity());
    out_of_range_assert(size <= N, "flat_vector resize out of range");
    cursor_ = data_ + size;
  }

  constexpr void swap(flat_vector& other) noexcept {
    auto max = std::max(size(), other.size());
    std::swap_ranges(data_, data_ + max, other.data_);
    auto this_size = size();
    auto other_size = other.size();
    cursor_ = data_ + other_size;
    other.cursor_ = other.data_ + this_size;
  }

private:
  T data_[N];
  T* cursor_;
};

template <std::size_t N, typename T>
constexpr bool operator==(const flat_vector<N, T>& lhs,
                          const flat_vector<N, T>& rhs) {
  return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}

template <std::size_t N, typename T>
constexpr bool operator!=(const flat_vector<N, T>& lhs,
                          const flat_vector<N, T>& rhs) {
  return !(lhs == rhs);
}

template <std::size_t N, typename T>
constexpr bool operator<(const flat_vector<N, T>& lhs,
                         const flat_vector<N, T>& rhs) {
  return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(),
                                      rhs.end());
}

template <std::size_t N, typename T>
constexpr bool operator<=(const flat_vector<N, T>& lhs,
                          const flat_vector<N, T>& rhs) {
  return !(rhs < lhs);
}

template <std::size_t N, typename T>
constexpr bool operator>(const flat_vector<N, T>& lhs,
                         const flat_vector<N, T>& rhs) {
  return rhs < lhs;
}

template <std::size_t N, typename T>
constexpr bool operator>=(const flat_vector<N, T>& lhs,
                          const flat_vector<N, T>& rhs) {
  return !(lhs < rhs);
}

} // namespace es

namespace std {
template <std::size_t N, typename T>
constexpr void swap(es::flat_vector<N, T>& lhs,
                    es::flat_vector<N, T>& rhs) noexcept {
  lhs.swap(rhs);
}

template <std::size_t N, typename T, typename U>
constexpr typename es::flat_vector<N, T>::size_type
erase(es::flat_vector<N, T>& c, const U& value) {
  auto first = std::remove(c.begin(), c.end(), value);
  auto count = std::distance(first, c.end());
  c.resize(std::distance(c.begin(), first));
  return count;
}

template <std::size_t N, typename T, typename Pred>
constexpr typename es::flat_vector<N, T>::size_type
erase_if(es::flat_vector<N, T>& c, Pred pred) {
  auto first = std::remove_if(c.begin(), c.end(), pred);
  auto count = std::distance(first, c.end());
  c.resize(std::distance(c.begin(), first));
  return count;
}
} // namespace std

#endif // ESTD___CONTAINER_FLAT_VECTOR_H
